package Sort;

public class HeapSort {

    public static void sort(int[] a){
        heapify(a,a.length);
        for (int right = a.length - 1; right > 0; right--){
            swap(a,0,right);
            down(a,0,right);
        }
    }

    public static void heapify(int[] arr, int size){
        for(int i=size/2-1; i>=0; i--){
            down(arr, i, size);
        }
    }

    public static void down(int[] array,int parent,int size){
        while(true){
            int left=parent*2+1;
            int right=left+1;
            int max =parent;

            if(left<size && array[left]>array[max]){
                max=left;
            }
            if (right<size && array[right]>array[max]){
                max=right;
            }

            if(max==parent){
                break;
            }else{
                swap(array,max,parent);
            }
        }

    }

    public static void swap(int []array,int a,int b){
        int temp=array[a];
        array[a]=array[b];
        array[b]=temp;
    }
}
